1. Field of the Invention
The present invention relates to a decoding apparatus, a decoding method, and a decoding program, and more particularly, to a decoding apparatus, a decoding method, and a decoding program, which can be implemented in a low-complexity circuit configuration.
2. Description of the Related Art
In communication systems, coding is used to achieve high reliability even when communication is performed over a communication channel having noise. For example, wireless (radio) communication systems such as a satellite network are exposed to noise caused by geographical or environmental factors. Communication channels have a theoretical limit known as the Shannon's limit on the communication capacity represented by the number of bits per symbol for a particular signal-to-noise ratio. Coding algorithms are designed so as to achieve as high a rate as possible within the Shannon's limit. This requirement is important in particular in design of the coding algorithm for use in bandwidth-limited satellite systems.
Turbo code such as PCCC (Parallel Concatenated Convolutional Codes) codes or SCCC (Serially Concatenated Convolutional Codes) codes are used to achieve high performance close to the Shannon's limit. Low density parity check codes (LDPC) have been known for many decades. Recently, LDPC codes have significant attention because of its high performance rediscovered recently.
The LDPC coding was first proposed by R. G. Gallager in “Low Density Parity Check Codes” (R. G. Gallager, Cambridge, Mass., M. I. T. Press, 1963) and has been recently rediscovered by D. J. C. MacKay (“Good error correcting codes based on very parse matrices”, Submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999) and M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman (“Analysis of low density codes and improved designs using irregular graphs”, in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998).
Recent research studies have revealed that the performance of LDPC codes increases with the code length, and LDPC codes with sufficiently large length can provide good performance, similar to that of turbo codes, close to the Shannon's limit. LDPC codes have a feature that the minimum distance is proportional to the code length and thus low block error probabilities can be achieved. Besides, LDPC codes have substantially no error floors which can occur in decoding of turbo codes.
Because of the advantages described above, LDPC codes have been employed in the DVB-S.2 standard (established by ETSI (European Telecommunication Standard Institute) that will be a successor of the DVB-S standard currently employed in many countries world-wide.
A bit deinterleaving algorithm and a decoding algorithm of LDPC codes are described below using a specific example in which a transmitted signal according to the DVB-S.2 standards is received by a receiver. LDPC codes are linear code and they do not necessarily need to be binary. However, binary LDPC codes are used in the DVB-S.2 standard, and thus in the following discussion, it is assumed that LDPC codes used are binary.
FIG. 1 illustrates an example of a functional configuration of a transmitter according to the DVB-S.2 standard.
The transmitter includes a mode adapter 11, a stream adapter 12, an FEC encoder 13, a mapping unit 14, a physical layer scrambler and synchronization pilot signal insertion unit 110 and a modulator 111.
Each data output from each functional block is denoted by a combination of an alphabetic character D and a numeral so as to distinguish among data output from various functional blocks. Names of output data of blocks are not necessarily given such that the same name is given for output data in the same block. On the contrary, depending on the situation, the same name is used for output data of different blocks. When data are the same in symbol but different in name, these data are basically output data in the same functional block, but different names are used depending on the context. For example, different names are used depending on units being discussed. Conversely, when data are the same in name but different in symbol, the same name is used because the data are similar in feature, but different symbols are used because they are output from different functional blocks, that is, in this case, these data are not the same in the strict sense. This can occur, for example, for relocated data and its original data. Note that the manner of assigning names and symbols to data explained in this paragraph is applied to the entire description.
The transmitter according to the DVB-S.2 is explained below in terms of its functions.
An input stream D101 is supplied to the mode adapter 11 and is subjected to a process described below, and a result is output as a stream D106. Note that the input stream D101 may be a single input stream or a plurality of input streams.
The mode adapter 11 includes an input interface 101, a CRC-8 encoder 102, and a merger/slicer 103, and baseband header output unit 104.
In the mode adapter 11, the input stream D101 is input to the input interface 101 and output as a stream D102 from the input interface 101 to the CRC-8 encoder 102.
In the CRC-8 encoder 102, of the input stream D102 supplied from the input interface 101, a user packet part excluding a synchronization byte is CRC-8 encoded, and a user packet stream D103 obtained as a result of the CRC-8 encoding is supplied to the merger/slicer 103.
The CRC-8 encoded user packet stream D103 is sliced by the merger/slicer 103 and rewritten in a data field D104.
The user packet stream rewritten in the data field D104 is merged with a baseband header D105 output from the baseband header output unit 104. The result is output as a baseband frame D106 from the mode adapter 11 to the stream adapter 12.
In a baseband scrambler 105 of the stream adapter 12, the baseband frame D106 is scrambled in accordance with a pseudo random binary sequence generation polynomial. The resultant scrambled baseband frame D107 is supplied to the FEC encoder 13.
The FEC encoder 13 includes a BCH encoder 106, an LDPC encoder 107, and a bit interleaver 108.
The scrambled baseband frame D107 is supplied to the BCH encoder 106 in the FEC encoder 13 and is BCH-coded. The result is supplied as an output D108 to the LDPC encoder 107. In the LDPC encoder 107, the output D108 supplied from the BCH encoder 106 is LDPC-coded, and the result is supplied as an output D109 to the bit interleaver 108. In the bit interleaver 108, the output D109 supplied from the LDPC encoder 107 is bit-interleaved. As a result, an FEC frame D110 is obtained. The resultant FEC frame D110 is output from the FEC encoder 13 to the mapping unit 14. Note that for QPSK data, the bit interleaving is not performed.
The bit interleaving process is described in further detail below.
In the DVB-S.2 standard, two values are allowed as a code length n. One allowable value of the code length is 64800 bits, and this code length is referred to as a normal FEC frame length. The other one is 16200 bits and is referred to as a short FEC frame length. The length k of an information word to be subjected to LDPC coding is given by the product of the code length n and a coding rate r.
When the information word input to the LDPC encoder 107 is data of a sequence of bits taking a value of 0 or 1 with a length k=P×k0, and a codeword output from the LDPC encoder 107 is data of a sequence of bits taking a value of 0 or 1 with a total length n=P×n0 as shown in FIG. 2, a parity check matrix used by an LDPC decoding calculation unit (described later with reference to FIG. 6) has n−k rows and n columns and its element has a value of 0 or 1. In this parity check matrix, a part with a length of k on the left-hand side is referred to as an information part, and a part with a length of n−k on the right-hand side is referred to as a parity part.
In this case, the bit interleaving scheme used by the bit interleaver 108 is determined by the modulation scheme and the coding rate r.
More specifically, FIG. 3 illustrates a bit interleaving scheme for 8PSK data with the normal FEC frame length (64800 bits). FIG. 4 illustrates a bit interleaving scheme for 16APSK data with the normal FEC frame length (64800 bits). FIG. 5 illustrates a bit interleaving scheme for 32APSK data with the normal FEC frame length (64800 bits).
In FIGS. 3 to 5, the received value (D109 supplied from the LDPC encoder 107, in the example shown in FIG. 1) is written in a direction along columns as represented by solid arrows, and read out in a direction along rows as represented by dotted arrows and supplied to the mapping unit 14 (and finally to the FEC decoder). That is, in the bit interleaver 108, data is sequentially written in the direction along columns and sequentially read out in the direction along rows. However, exceptionally, for 8PSK data with a coding rate of ⅗, data is read out as represented by broken arrows in FIG. 3.
Each given codeword is arranged by the bit interleaver 108 into the form of a matrix, and each one of 3 to 5 boxes shown in FIGS. 3 to 5 denotes a column of the matrix in which one codeword is arranged. In any of FIGS. 3 to 5, the number of rows×the number of columns=64800.
More specifically, the number of columns is determined by the number of bits of one signal point (one symbol). For example, for 8 (=23) PSK data, the data is arranged in 3 columns as shown in FIG. 3. For 16 (=24) APSK data, the data is arranged in 4 columns as shown in FIG. 4. For 32 (=25) APSK data, the data is arranged in 5 columns as shown in FIG. 5. On the other hand, the number of rows is given by the quotient obtained by dividing 64800 by the number of columns. More specifically, for 8 (=23) PSK data, the data is arranged in 21600 rows as shown in FIG. 3. For 16 (=24) APSK data, the data is arranged in 16200 rows as shown in FIG. 4. For 32 (=25) APSK data, the data is arranged in 12960 rows as shown in FIG. 5.
Referring again to FIG. 1, the FEC frame D110 obtained as a result of the bit interleaving process performed by the bit interleaver 108 in the above-described manner is output from the FEC encoder 13 to a bit mapper 109 in the mapping unit 14 and mapped thereby in accordance with a predetermined modulation scheme. The data is then applied to the modulator 111 via the physical layer scrambler and synchronization pilot signal insertion unit 110 whereby the data is modulated. The resultant data is finally output as a transmit signal D113.
The transmit signal (the transmit signal D113 in the example shown in FIG. 1) transmitted from the transmitter configured as described above with reference to FIG. 1 is received by a receiver including a functional block adapted to perform an LDPC decoding on the received data. Hereinafter, this block will be referred to as an LDPC decoding apparatus. FIG. 6 illustrates an example of a configuration of such an LDPC decoding apparatus. In the example shown in FIG. 6, the LDPC decoding apparatus includes a demapping unit 151 and an LDPC decoder (including associated parts) 152.
The transmit signal (the transmit signal D113 in the example shown in FIG. 1) transmitted from the transmitter shown in FIG. 1 is input as a received value D201 to the receiver. In the receiver, the received value D201 is applied to a bit demapper 201 in the demapping unit 151. The bit demapper 201 demaps the received value D201 in accordance with the modulation scheme of the signal. The result is supplied as an output D202 to the LDPC decoder (including associated parts) 152.
More specifically, the LDPC decoder (including associated parts) 152 includes a bit deinterleaver 202 and an LDPC decoder 153. The output D202 from the bit demapper 201 is input to the bit deinterleaver 202.
In the bit deinterleaver 202, the output D202 from the bit demapper 201 is bit-interleaved. That is, the output D202 in the form interleaved by the bit interleaver 108 shown in FIG. 1 is deinterleaved into the original form, and the result is supplied as an output D203 from the bit deinterleaver 202 to the LDPC decoder 153.
The LDPC decoder 153 includes a receiving unit 203, an LDPC decoding calculation unit 204, and a decoded result memory 205.
The output D203 from the bit deinterleaver 202 is applied to the receiving unit 203 of the LDPC decoder 153. In the receiving unit 203, the data is subjected to a parity permutation process and is temporarily stored therein until the stored data reaches one codeword. Each time one codeword is obtained, the codeword is read out as output D204 from the receiving unit 203 and supplied to the LDPC decoding calculation unit 204.
The LDPC decoding calculation unit 204 performs an LDPC decoding calculation on the output D204 to obtain decoded data. The resultant decoded data D205 produced by the LDPC decoding calculation unit 204 is output as a decoded word D206 to the outside via the decoded result memory 205. In this process, in order for the LDPC decoder 153 to more precisely perform the LDPC decoding calculation, received values are generally in the form of soft values.
Referring to FIG. 6, the LDPC decoder (including associated parts) 152 in the receiver according to the DVB-S.2 standard is described in further detail below, in terms of their functions.
The bit deinterleaving performed by the bit deinterleaver 202 is a process inverse to bit interleaving performed by the bit interleaver 108 (FIG. 1). Therefore, the scheme of the bit deinterleaving process performed by the bit deinterleaver 202 depends on the modulation scheme and the coding rate r used on the transmitting end.
More specifically, FIG. 7 illustrates a bit deinterleaving scheme corresponding to the bit interleaving scheme shown in FIG. 3, that is, this bit deinterleaving scheme is used for 8PSK data with the normal FEC frame length (64800 bits). FIG. 8 illustrates a bit deinterleaving scheme corresponding to the bit interleaving scheme shown in FIG. 4, that is, this bit deinterleaving scheme is used for 16APSK data with the normal FEC frame length (64800 bits). FIG. 9 illustrates a bit deinterleaving scheme corresponding to the bit interleaving scheme shown in FIG. 5, that is, this bit deinterleaving scheme is used for 32APSK data with the normal FEC frame length (64800 bits).
In FIGS. 7 to 9, the received value (D202 output from the bit demapper 201, in the example shown in FIG. 6) is written in a direction along rows as represented by solid arrows, and read out in a direction along columns as represented by dotted arrows and supplied to an FEC decoder (the LDPC decoder 153, in the specific example shown in FIG. 6).
In FIGS. 7 to 9, as in FIGS. 3 to 5, each given codeword is arranged by the bit deinterleaver 202 into the form of a matrix, and each one of 3 to 5 boxes denotes a column of the matrix in which one codeword is arranged. In any of FIGS. 7 to 9, the number of rows×the number of columns=64800.
More specifically, the number of columns is determined by the number of bits of one signal point (one symbol). For example, for 8 (=23) PSK data, the data is arranged in 3 columns as shown in FIG. 7. For 16 (=24) APSK data, the data is arranged in 4 columns as shown in FIG. 8. For 32 (=25) APSK data, the data is arranged in 5 columns as shown in FIG. 9. On the other hand, the number of rows is given by the quotient obtained by dividing 64800 by the number of columns. More specifically, for 8 (=23) PSK data, the data is arranged in 21600 rows as shown in FIG. 7. For 16 (=24) APSK data, the data is arranged in 16200 rows as shown in FIG. 8. For 32 (=25) APSK data, the data is arranged in 12960 rows as shown in FIG. 9.
That is, in the bit deinterleaving process, as described above with reference to FIGS. 7 to 9, data is sequentially written in the direction along rows and sequentially read out in the direction along columns. However, exceptionally, for 8PSK data with a coding rate of ⅗, data is written as represented by broken arrows in FIG. 9.
More specifically, for 8PSK data with the normal FEC frame length (64800 bits), the matrix structure shown in FIG. 7 has 21600 rows×3 columns (each element corresponds to 1 bit). In this structure, one received symbol is written in one row (with a length of 3 bits), while reading is performed column by column.
If the bit deinterleaver 202 is configured such that reading and writing from/to a single storage unit is performed at the same time, a new value is written in the direction along rows before reading in the direction along columns is completed. This can cause an error to occur in the reading operation, and thus correct data is not supplied to the LDPC decoder 153. Thus, to avoid the above problem, the actual bit deinterleaver 202 has two storage units 221 and 222 disposed in parallel as shown in FIG. 10 or 11, and reading and writing are performed alternately for these two storage units 221 and 222 such that when reading is performed to one storage unit, writing is performed to the other thereby preventing data being read out from being overwritten.
In general, a RAM (Random Access Memory) capable of writing/reading data to/from an arbitrary specified address is used as the storage devices 221 and 222.
In the above-described receiver according to the DVB-S.2 standard, the bit deinterleaving process is performed by the bit deinterleaver 202 disposed outside the LDPC decoder 153.
Referring again to FIG. 6, after being subjected to the bit deinterleaving process by the bit deinterleaver 202, the data is output as data D203 from the bit deinterleaver 202 and supplied to the LDPC decoder 153. The LDPC decoder 153 performs LDPC-decoding on the received data D203.
More specifically, the LDPC decoder 153 performs the LDPC decoding using a parity check matrix with n−k rows and n columns whose elements take a value of 0 or 1, where n−k=P×(n0−k0) and n=P×n0. In this process, the LDPC decoder 153 regards a part with a length k=P×k0 on the left-side of the parity check matrix as an information part, and the remaining part with a length n−k=P×(n0−k0) as a parity part.
Note that the LDPC decoding calculation process is performed using a parity check matrix in the form of an array of zero matrices, matrices obtained by cyclically shifting a P×P unit matrix, and/or matrices obtained by adding arbitrary such matrices, by using a parity check matrix that can be changed into such a form via row/column permutation, the LDPC decoding process can be performed at a high speed by configuring the LDPC decoding calculation unit 204 so as to include P calculation units and by using these P calculation units in parallel.
Parity check matrices used in the DVB-S.2 systems can be converted, by row/column permutation, into matrices of the form described above.
In view of the above, in order to achieve high-speed LDPC decoding using P parallel operation units, the LDPC decoder 153 according to the DJB-S.2 standard performs row/column permutation to convert a given original parity check matrix into the above-describe form.
If the parity check matrix is subjected to the row/column permutation, the resultant parity check matrix has a different parity part from that of the original parity check matrix, although the information part remains unchanged. Note that there is a particular relation between column numbers before and after the column permutation. That is, if the columns in the parity part are numbered such that the first column in the parity part is referred to as a 0th column, ((n0−k0)×i+j)th columns (0≦i≦P−1 and 0≦j≦n0−k0−1) before the column permutation are moved into (P×j+i)th columns via the column permutation.
Therefore, in this scheme, it is required that the received values should also be treated in the order corresponding to the columnpermutation. More specifically, when the received values are subjected to the LDPC decoding calculation process (by the LDPC decoding calculation unit 204 shown in FIG. 6), the received values located in the original columns are moved into the permutated columns.
Therefore, when received values supplied as the output D203 from the bit deinterleaver 202 are written in the receiving unit 203 of the LDPC decoder 153, the received values are relocated into the order of permutated columns so that the parity check matrix obtained via the parity permutation can be applied to the received values. This process of relocating the locations of received values performed by the receiving unit 203 is referred to as parity permutation.
For example, when a code represented by a parity check matrix shown in FIG. 12 is LDPC-decoded, the parity permutation is performed as follows.
Note that in FIG. 12, elements of “0” in the parity check matrix are denoted by “.”, and also note that the code expressed by the parity check matrix shown in FIG. 12 has a code length of 108 and a coding rate r=⅔, and thus n=108 and k=72.
In FIG. 13, the parity check matrix shown in FIG. 12 is expressed in the form of a collection of submatrices each having 6 (=P) rows and 6 (=P)columns (hereinafter, each submatrix will be denoted as 6×6 submatrix). These 6×6 (P×P) submatrices include the following types: 6×6 unit matrices; matrices obtained by replacing one of 1s in a 6×6 unit matrices by 0; matrices produced by cyclic shift of one of the above matrices; matrices produced by the sum of some of the above matrices; and 6×6 matrices whose elements are all 0.
That is, the parity check matrix shown in FIG. 13 is obtained by arranging 6×6 submatrices of the above-described types such that as many submatrices as n0−k0=n/P−k/P=6 are arranged in the vertical direction, and as many submatrices as n0=n/P=18 are arranged in the horizontal direction.
Note that the matrix shown in FIG. 13 is in a state in which the column permutation has been carried out, and thus the order of columns in the parity part is different from the order in a state in which the column permutation is not yet carried out.
On the left-hand side of FIG. 14, shown is a parity part which is not yet subjected to the row/column permutation. On the right-hand side of FIG. 14, shown is a parity part in a row/column-permutated form. FIG. 15 illustrates, in an enlarged manner, the parity part shown on the left-hand side of FIG. 14 which is not yet subjected to the row/column permutation. FIG. 16 illustrates a parity part which has already been subjected to row permutation but not yet column permutation. FIG. 17 illustrates a parity part which has already been subjected to row permutation and further column permutation, that is, this figure shows, in an enlarged form, the parity shown on the right-hand side of FIG. 14.
As can be seen by comparing FIGS. 16 and 17, columns located in ((n0−k0)×i+j)th positions, i.e., (6×i+j)th positions are moved into (P×j+i)th positions, i.e., (6×j+i)th positions via the column permutation, where 0≦i≦P−1=5 and 0≦j≦n0−k0−1=5.
In order for the parity check matrix subjected to column permutation to work in the intended manner as described above, the parity part of the received value should be permutated such that data located in a ((n0−k0)×i+j)th position, i.e., (6×i+j)th position is moved into a (P×j+i)th position, i.e., (6×j+i)th position for all values of i and j satisfying 0≦i≦P−1=5 and 0≦j≦n0−k0−1=5, where data are numbered starting from 0 for the first data of the parity part of the received value.
A specific example of a parity permutation scheme is described below.
In the above-described receiver (FIG. 6) according to the DVB-S.2 standard, the parity permutation is carried out by the receiving unit 203 of the LDPC decoder 153.
Now, implementation of the P=6 parallel LDPC decoding calculation by the LDPC decoding calculation unit 204 of the LDPC decoder 153 is discussed below. To achieve the implementation, the LDPC decoding calculation unit 204 is assumed to include six calculation units adapted to perform the LDPC decoding calculation process in parallel. Hereinafter, a set of these six calculation units will be collectively referred to as a 6 parallel LDPC decoding calculation unit.
A codeword is represented by a parity check matrix. On the top of FIG. 18, shown is a codeword represented by the example of the parity check matrix shown in FIG. 13. The receiving unit 203 of the LDPC decoder 153 has a storage device 231 including a RAM having a configuration with a horizontal size corresponding to a word-length of 108/6=18 and a vertical size that allows as many received values as P=6 to be stored per word and thus having a total storage capacity of 30 bits×18 words, as shown on the bottom of FIG. 18. Hereinafter, this storage device 231 will also be referred to as a received value memory 231.
When received values each quantized in 5 bits are serially input in the form of soft values to the received value memory 231, and written until one complete codeword is written in the received value memory 231. In the reading operation, received values are read out from the received value memory 231 in parallel in a word-by-word basis, that is, 6 received values are read out in parallel at the same time for each word (each ellipse Ru shown on the bottom of FIG. 18 denotes one word including 6 received values). Thus 6 received values of each word are simultaneously input to the LDPC decoding calculation unit 204 word by word, thereby allowing the 6 parallel LDPC decoding calculation unit of the LDPC decoding calculation unit 204 to perform the LDPC decoding calculation process in a parallel manner.
For convenience in the following explanation, an unit called a bit-direction number is introduced herein.
That is, the received value memory 231 is equally divided into P parts in the direction along the bit width, and the respective parts are numbered 0, 1, . . . , P−1 starting from the most significant bit (MSB). The numbers defined in this manner are referred to as bit-direction numbers. Thus, received values in the form of soft values are serially stored in the received value memory 231 such that one received value is stored in one of P zones (each assigned one bit-direction number).
More specifically, in the present example, as shown on the bottom of FIG. 18, the received value memory 231 with a width of 30 bits is equally divided every 5 bits into P=6 parts in the direction along the width, and the respective parts are numbered 0, 1, . . . , P−1 starting from the most significant bit (MSB). Thus, bit-direction numbers are defined.
As shown on the top of FIG. 18, the elements of one codeword supplied from the receiving unit 203 are serially numbered starting from 0 for the first element. That is, the first element is numbered 0, and the number is incremented by 1 element by element for the following elements. Hereinafter, the codeword read out from the receiving unit 203 will be referred to as an output codeword, and numbered elements of the output codeword will be referred to as data elements. In the following discussion, received values correspond to particular data elements of the output codeword.
To write received values, which are serially input to the receiving unit 203, at correct locations in the received value memory 231, the received value memory 231 in the receiving unit 203 is realized using a partially writable RAM capable of storing data at any specified location.
In the received value memory 231, the data elements of the output codeword are written at storage locations denoted by numerals in a box shown on the bottom of FIG. 18 illustrating the structure of the received value memory 231. That is, the data elements of the output codeword are sequentially written in the received value memory 231 in ascending order of the bit-direction number. More specifically, a (P×x+y)th data element of the output codeword is written in the received value memory 231 at a location (x, y) where x is the bit-direction number and y is the word-direction address.
In the receiving unit 203 having the received value memory 231 configured in the above-described manner, the parity permutation process is performed as follows.
Received values from the first arrival to a kth arrival to the receiving unit 203 as counted starting from the first received value of the received word correspond to the information part. For such received values corresponding to the information part, writing on the received value memory 231 is performed such that the received values are simply stored sequentially in the same order as the arrival order starting with the first data element of the codeword.
In the present case, k=72, and thus, for example, a received value of a 60th arrival as counted starting from the first received value of the received word is a received value of an arrival before the kth i.e., 72th arrival, and thus this received value belongs to the information part. Therefore, this received value belonging to the information part is stored in the received value memory 231 at a 60th location as counted from the location for the first data element of the codeword.
On the other hand, received values in the range from the kth one as counted with respect to the first received value of the received word and those following the kth one, that is, received values whose arrival order is given by k+(n0−k0)×i+j=72+6×i+j correspond to the parity part. Therefore, the received values corresponding to the parity part with the above-described arrival order, that is, k+(n0−k0)×i+j=72+6×i+j, are simply stored in the received value memory 231 at locations of k+P×j+i=72+6×j+i.
For example, a received value of an arrival number of k+(n0−k0)×2+1=72+6×2+1=85 as counted with respect to the first received value of the received word belongs to the parity part, and thus this received value is stored in the received value memory 231 at a location of k+P×1+1=72+6×1+2=80 as counted with respect to the location for the first data element of the codeword.
Because the data elements of the output codeword are sequentially written in the received value memory 231 in ascending order of the bit-direction number as described above, a (P×x+y)th data element of the output codeword is written in the received value memory 231 at a location (x, y) where x is the bit-direction number and y is the word-direction address.
From the point of view of the writing process, the received word is serially input to the receiving unit 203. Therefore, received values from the value of the first arrival value to a value of a kth arrival to the receiving unit 203 as counted starting from the first received value of the received word correspond to the information part. Thus, as shown on the top of FIG. 19, as long as the input received values are those belonging to the information part, the received values are simply written sequentially in the bit direction.
In the structure of the received value memory 231 shown on the top FIG. 19, numerals in a box indicate the serial arrival order of the received values of the received word arriving at the receiving unit 203. On the other hand, in the structure of the received value memory 231 shown on the bottom of FIG. 19, as with the diagram shown on the bottom of FIG. 18, numerals in a box indicate the serial numbers assigned to the respective data element of the output codeword (the serial numbers assigned to the respective storage locations) read from the received value memory 231 and supplied to the LDPC decoding calculation unit 204 (FIG. 6).
The writing operation is explained in further detail below with reference to the diagram on the top of FIG. 19 in conjunction with a numerals described in the diagram on the bottom of FIG. 19. The received values of (P×x+y)th arrival, (P×x+y+1)th arrival, . . . as counted starting from the first received value of the received value, that is, the received values corresponding to the information part are directly written at locations of x, x, . . . in word-direction address and y, y+1, . . . in bit-direction number. For example, as can be seen from the figures on the top and the bottom of FIG. 19, received values of 60th and 61st arrivals (see the diagram on the top of FIG. 19) as counted starting from the first received value of the received word are written at simply corresponding storage locations for the 60th and 61st data elements (see the diagram on the bottom of FIG. 19) of the output codeword.
Subsequently, received values corresponding to the parity part arrive. For these received values, writing is performed as follows. That is, received values of (k+(n0−k0)×i+j)th arrival, (k+(n0−k0)×i+j+1)th arrival, . . . corresponding to the parity part are written at locations of k0+j, k0+j+1, . . . in word-direction address and i, i, . . . in bit-direction number on the received value memory 231. That is, the received values corresponding to the parity part are sequentially written in the word direction on the received value memory 231, thereby achieving the parity permutation.
For example, in FIG. 19, a received value of (k+(n0−k0)×2+1)=72+6×2+1=85th arrival and a received value of (k+(n0−k0)×2+2)=72+6×2+2=86th arrival are written in the word direction on the received value memory 231 as can be seen from the diagram on the top of FIG. 19. In this case, it can be seen from the diagram on the bottom of FIG. 19 that the writing locations of the received values of 85th, 86th, . . . arrivals (denoted by numerals 85, 86, . . . in the diagram on the top of FIG. 19) corresponds to the storage locations (denoted by numerals 80, 86, . . . in the diagram on the bottom of FIG. 19) for k+P×1+2=72+6×1+2=80th, k+P×2+2=72+6×2+2=86th data elements and so on of the output codeword.
By writing the received values serially input to the receiving unit 203 at particular locations on the received value memory 231 in the above-described manner, it becomes possible to achieve the parity permutation corresponding to the column-permutation of the parity check matrix.
After one codeword is completely written via the above-described process including the parity permutation process, the received values are read from the received value memory 231 in parallel in units of words (consisting of 6 received values) each located in one of columns (ellipses) Ru shown in the diagram on the bottom of FIG. 18 and supplied to the LDPC decoding calculation unit 204 thereby making it possible for the 6 parallel LDPC decoding calculation unit in the LDPC decoding calculation unit 204 to perform the LDPC decoding calculation in parallel.
To achieve the above-described parity permutation process, it is required that the received values should be serially input to the receiving unit 203 and the receiving unit 203 should have the storage device 231 (such as a partially writable received value memory 231) capable of storing serially input received values at any specified storage locations.
Referring again to FIG. 6, after the bit deinterleaving by the bit deinterleaver 202 and the parity permutation by the receiving unit 203, the resultant deinterleaved received value D204 is input to the LDPC decoding calculation unit 204, subjected to the LDPC decoding calculation process, and the result is output as a decoded result D205.
In the above process, the LDPC decoding calculation unit 204 uses the matrix whose parity part is permuted in the above-described manner. Therefore, the parity part of received values is used in the order corresponding to the permutation in the LDPC decoding calculation process, and the result is output as decoded result D205 in the corresponding order. That is, the decoded result D205 obtained as a result of the LDPC decoding calculation process is in the order of the column number corresponding to the column permutation.
Therefore, before a decoded word D206 is output from the decoded result memory 205, it is required to re-arrange the order of the decoded result D205 into the original column order in the state not yet column-permutated. That is, the decoded result D205 provided by the LDPC decoding calculation unit 204 is stored in the decoded result memory 205 in the permutated column order. Thus, the rearrangement is carried out, and the decoded word D206 is output in the original column order in the state not subjected to the column permutation.
Note that no change occurs in terms of column order in the information part via the LDPC decoding calculation process performed by the LDPC decoding calculation unit 204. However, a change occurs in the parity part. Therefore, it is necessary to perform a process inverse to the parity permutation described above to rearrange the parity part in an order opposite to the order in which the parity permutation is performed so as to rearrange the decoded result into the original order of column numbers not yet subjected to the column permutation thereby obtaining the decoded word D206 having the same order of column numbers as the original order.
As described above, the LDPC decoder 153 includes the received value memory (the received value memory 231 in the receiving unit 203 shown in FIG. 18) having the storage capacity corresponding to the code length and the decoded result memory 205 whereby received values are stored in the parity-permutated form in the received value memory and the decoded result is read out in the inversely parity-permutated from the decoded result memory 205. At a stage in front of the LDPC decoder 153, there is disposed the bit deinterleaver 202 including two received value memories (the storage devices 221 and 222 shown in FIG. 10 or 11) each having a storage capacity corresponding to the code length.